/**
 * 二叉树的单旋操作
 * - 单旋操作根据二叉树的后序遍历(左子树 -> 右子树 -> 根节点)
 *
 * RR左旋(左单旋)：
 * - 旋转节点:当前不平衡的节点
 * - 新跟节点:旋转节点子树的根节点
 * - 变化分支:旋转节点的右子树的左子树
 * - 不变分支:旋转节点的右子树的右子树
 *
 * LL右旋(右单旋)：
 * - 旋转节点:当前不平衡的节点
 * - 新跟节点:左子树的根节点
 * - 变化分支:旋转节点的左子树的右子树
 * - 不变分支:旋转节点的左子树的左子树
 *
 * 第一种(RR)：
 * - 旋转节点 B，新跟节点 C，变化分支 D，不变分支 E
 *        A                A
 *      /   \            /   \
 *     F     B          F     C
 *    / \     \        / \   / \
 *   G   H     C      G   H B   E
 *            / \            \
 *           D   E            D
 *
 * 第二种(RR)：
 * - 旋转节点 B，新跟节点 C，变化分支 _，不变分支 E
 *        A                A
 *      /   \            /   \
 *     F     B          F     C
 *    / \     \        / \   / \
 *   G   H     C      G   H B   E
 *              \
 *               E
 *
 * 第三种(RR)：
 * - 旋转节点 B，新跟节点 C，变化分支 _，不变分支 D
 * - 旋转节点 A，新跟节点 C，变化分支 B，不变分支 D
 *   A          A
 *    \          \
 *     B          C        C
 *      \        / \      / \
 *       C      B   D    A   D
 *        \               \
 *         D               B
 *
 * 第四种(LL)：
 * - 旋转节点 B，新跟节点 C，变化分支 E，不变分支 D
 *          A              A
 *        /   \          /   \
 *       B     F        C     F
 *      /     / \      / \   / \
 *     C     G   H    D   B G   H
 *    / \                /
 *   D   E              E
 *
 * 第五种(LL)：
 * - 旋转节点 B，新跟节点 C，变化分支 _，不变分支 D
 *          A              A
 *        /   \          /   \
 *       B     E        C     E
 *      /     / \      / \   / \
 *     C     F   G    D   B F   G
 *    /
 *   D
 *
 * 第六种(LL)：
 * - 旋转节点 B，新跟节点 C，变化分支 _，不变分支 D
 * - 旋转节点 A，新跟节点 C，变化分支 B，不变分支 D
 *         A        A
 *        /        /
 *       B        C          C
 *      /        / \        / \
 *     C        D   B      D   A
 *    /                       /
 *   D                       B
 *
 * 第七种(LL+RR)：
 * - 旋转节点 B，新跟节点 C，变化分支 _，不变分支 D
 * - 旋转节点 E，新跟节点 F，变化分支 _，不变分支 G
 *         A                A                A
 *       /   \            /   \            /   \
 *      B     E          C     E          C     F
 *     /       \        / \     \        / \   / \
 *    C         F      D   B     F      D   B E   G
 *   /           \                \
 *  D             G                G
 *
 */


class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 需要左旋的树
const LA = new TreeNode("A");
const LB = new TreeNode("B");
const LC = new TreeNode("C");
const LD = new TreeNode("D");
const LE = new TreeNode("E");
const LF = new TreeNode("F");
const LG = new TreeNode("G");
const LH = new TreeNode("H");
LA.left = LF;
LA.right = LB;
LF.left = LG;
LF.right = LH;
LB.right = LC;
LC.right = LE;
LC.left = LD;
// 需要右旋的树
const RA = new TreeNode("A");
const RB = new TreeNode("B");
const RC = new TreeNode("C");
const RD = new TreeNode("D");
const RE = new TreeNode("E");
const RF = new TreeNode("F");
const RG = new TreeNode("G");
const RH = new TreeNode("H");
RA.left = RB;
RA.right = RF;
RB.left = RC;
RC.left = RD;
RC.right = RE;
RF.left = RG;
RF.right = RH;
// 需要右旋+左旋的树
const RLA = new TreeNode("A");
const RLB = new TreeNode("B");
const RLC = new TreeNode("C");
const RLD = new TreeNode("D");
const RLE = new TreeNode("E");
const RLF = new TreeNode("F");
const RLG = new TreeNode("G");
RLA.left = RLB;
RLB.left = RLC;
RLC.left = RLD;
RLA.right = RLE;
RLE.right = RLF;
RLF.right = RLG;


/**
 * 计算二叉树的最大深度
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {number} 返回二叉树的最大深度
 */
function getDeep(root) {
  // 如果节点为空，则深度为0
  if (root == null) return 0;
  // 递归计算左右子树的最大深度，并取较大值加1
  return Math.max(getDeep(root.left), getDeep(root.right)) + 1;
}

/**
 * 判断二叉树是否平衡
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {boolean} 如果二叉树是平衡的返回true，否则返回false
 */
function isBalance(root) {
  // 如果节点为空，则认为是平衡的
  if (root == null) return true;
  // 计算左子树的深度
  let leftDeep = getDeep(root.left);
  // 计算右子树的深度
  let rightDeep = getDeep(root.right);
  // 如果左右子树深度差超过1，则不平衡
  if (Math.abs(leftDeep - rightDeep) > 1) return false;
  // 递归判断左右子树是否平衡
  return isBalance(root.left) && isBalance(root.right);
}


/**
 * 执行一次左旋转操作
 * 左旋转常用于平衡二叉树，如AVL树，在插入或删除节点后以恢复树的平衡
 * 左旋转操作针对的是一个右重（右子树较左子树深）的节点，通过旋转使其左子树更深
 *
 * @param {TreeNode} root - 需要进行左旋转的根节点
 * @returns {TreeNode} - 旋转后的根节点
 */
function leftRotate(root) {
  // 新的根节点将是当前节点的右子节点
  let newRoot = root.right;
  // 原根节点的右子节点变为新根节点的左子节点
  root.right = root.right.left;
  // 新根节点的左子节点变为原根节点
  newRoot.left = root;
  // 返回新的根节点
  return newRoot;
}


/**
 * 执行一次右旋转操作，用于平衡二叉树
 * 右旋转操作通常用于处理树的左子树比右子树高的情况，以平衡树的高度
 * @param {TreeNode} root - 需要进行右旋转的节点，假设该节点及其左子树已经存在
 * @returns {TreeNode} - 旋转后的根节点，即原来的左子节点
 */
function rightRotate(root) {
  // 将左子节点设为新的根节点
  let newRoot = root.left;
  // 原根节点的左子节点变为原左子节点的右子节点
  root.left = root.left.right;
  // 新根节点的右子节点设为原根节点
  newRoot.right = root;
  // 返回新的根节点
  return newRoot;
}


/**
 * 将给定的二叉树转换为平衡二叉树
 * 如果给定的根节点已经是平衡的，则直接返回该根节点
 * 否则，递归地对左右子树进行转换，直到整棵树变为平衡二叉树
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {TreeNode} - 平衡化之后的二叉树的根节点
 */
function change(root) {
  // 检查当前根节点是否已经是平衡的
  if (isBalance(root)) return root;
  // 对左子树进行递归调用，以确保左子树也是平衡的
  if (root.left != null) root.left = change(root.left);
  // 对右子树进行递归调用，以确保右子树也是平衡的
  if (root.right != null) root.right = change(root.right);
  // 计算左子树的深度
  let leftDeep = getDeep(root.left);
  // 计算右子树的深度
  let rightDeep = getDeep(root.right);
  // 如果左右子树的深度差小于2，则当前根节点已经是平衡的
  if (Math.abs(leftDeep - rightDeep) < 2) {
    return root;
  } else if (leftDeep > rightDeep) {
    // 如果左子树比右子树深，则进行右旋转以平衡树
    return rightRotate(root);
  } else {
    // 如果右子树比左子树深，则进行左旋转以平衡树
    return leftRotate(root);
  }
}

const newRootL = change(LA);
console.log("▶『newRootL』", newRootL);
const newRootR = change(RA);
console.log("▶『newRootR』", newRootR);
const newRootRL = change(RLA);
console.log("▶『newRootRL』", newRootRL);
